package com.itheima.algorithm.recursion_single;

import java.util.Arrays;

/**
 * 递归插入排序
 * <ul>
 *     <li>将数组分为两部分 [0 .. low-1]  [low .. a.length-1]</li>
 *     <li>左边 [0 .. low-1] 是已排序部分</li>
 *     <li>右边 [low .. a.length-1] 是未排序部分</li>
 *     <li>每次从未排序区域取出 low 位置的元素, 插入到已排序区域</li>
 * </ul>
 */
public class E05InsertionSort {
    public static void sort(int[] a) {
        //开始就拿第二个元素进行插入
        insertion(a, 1);
    }

    public static void main(String[] args) {
        int[] a1 = {5, 6, 3, 2, 1};
        insertionLoop(a1);
        System.out.println(Arrays.toString(a1));
    }


    /**
     * <h3>循环实现</h3>
     *
     * @param a a
     */
    private static void insertionLoop(int[] a) {
        // 从第二个元素开始，逐个插入到已排序部分
        for (int low = 1; low < a.length; low++) {
            int temp = a[low]; // 待插入元素
            int index = low - 1; // 已排序区域的指针

            // 在已排序部分中找到合适的插入位置
            while (index >= 0 && a[index] > temp) {
                a[index + 1] = a[index]; // 空出插入位置
                index--; // 继续向左找
            }

            // 找到插入位置,如果说index+1= low,则说明temp插入位置就是index+1（temp就是最大的）
            if (index + 1 != low) {
                a[index + 1] = temp;
            }
        }
    }

    /**
     * <h3>递归函数 将 low 位置的元素插入至 [0..low-1] 的已排序区域</h3>
     *
     * @param a   数组
     * @param low 未排序区域的左边界
     */
    private static void insertion(int[] a, int low) {
        if (low == a.length) {
            return;
        }
        int temp = a[low];// 待插入元素
        int index = low - 1; //已经排序区域的指针

        //只要找到比temp小的原始的index，则将temp插入到index+1
        while (index >= 0 && a[index] > temp) {
            a[index + 1] = a[index]; //空出插入位置,此时index+1为插入位置
            index--; //继续向左找
        }
        // 找到插入位置,如果说index+1= low,则说明temp插入位置就是index+1（temp就是最大的）
        if (index + 1 != low) {
            a[index + 1] = temp;
        }

        insertion(a, low + 1);
    }

    // 另一种插入排序的实现,缺点: 赋值次数较多 (不推荐)
    private static void insertion2(int[] a, int low) {
        if (low == a.length) {
            return;
        }

        int i = low - 1;
        while (i >= 0 && a[i] > a[i + 1]) {
            int t = a[i];
            a[i] = a[i + 1];
            a[i + 1] = t;

            i--;
        }

        insertion2(a, low + 1);
    }


}
